﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

public class Solution143
{
    public void ReorderList(ListNode head)
    {
        //先找到中点，反转
        ListNode low = head;
        ListNode fast = head;
        while (fast != null&&fast.next!=null)
        {
            low=low.next;
            fast = fast.next.next;
            
        }

        ListNode right= ReverseList(low.next);

        low.next = null;

        ListNode cur =head;
        
        while (right!=null)
        {
            ListNode next = right.next;
            right.next = cur.next;
            cur.next = right;
            cur = right.next;
            right= next;

        }


   
    }

    private ListNode ReverseList(ListNode head)
    {
       

        ListNode dummy = new ListNode();
      


        while(head != null) {

            ListNode next = head.next;
            head.next = dummy.next;
            dummy.next = head;
            head = next;

        }
        return dummy.next;

    }
}
class Program143
{

    static void Main143(string[] args)
    {
        ListNode dummyHead = new ListNode();

        for (int i = 4; i > 0; i--)
        {
            ListNode listNode = new ListNode(i);

            listNode.next = dummyHead.next;
            dummyHead.next = listNode;
        }

        //ListNode listNode = new ListNode(3);
        //dummyHead.next = listNode;
        //ListNode listNode2 = new ListNode(5);
        //listNode.next = listNode2;
        Solution143 sol = new Solution143();
       sol.ReorderList(dummyHead.next);

        ListNode cur = dummyHead.next;
       
        while (cur != null)
        {
            Console.WriteLine(cur.val);
            cur = cur.next;
        }


    }
}